package week01

import "sort"

// 1. 两数之和
// https://leetcode-cn.com/problems/two-sum/

// 排序+双指针

// 还不如用 map

func twoSum(nums []int, target int) []int {
	var items = make([]item, len(nums))
	for i, v := range nums {
		items[i] = item{
			value: v,
			index: i,
		}
	}
	sort.Sort(itemSort(items))

	var l, r = 0, len(items)-1
	for l < r {
		if items[l].value + items[r].value == target {
			return []int{items[l].index, items[r].index}
		} else if items[l].value + items[r].value > target {
			r--
		} else {
			l++
		}
	}
	return []int{}
}

type item struct {
	value int
	index int
}

type itemSort []item
func(is itemSort) Less(i, j int) bool { return is[i].value < is[j].value }
func(is itemSort) Len() int { return len(is) }
func(is itemSort) Swap(i, j int) { is[i], is[j] = is[j], is[i] }